A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent disclosure, as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all copyright rights whatsoever.
The present disclosure is related to the disclosures provided in the following U.S. applications filed on even date herewith: xe2x80x9cIntelligent System for Generating and Executing a Sheet Metal Bending Plan,xe2x80x9d filed in the names of David Alan Bourne et al. U.S. Application Ser. No. 08/338,113 xe2x80x9cMethods for Backgaging and Sensor-Based Control of Bending Operations,xe2x80x9d filed in the names of David Alan Bourne et al. U.S. Application Ser. No. 08/338,153; and xe2x80x9cFingerpad Force Sensing System,xe2x80x9d filed in the names of Anne M. Murray et al. The contents of each of these related applications are expressly incorporated by reference herein in their entireties.
1. Field of the Invention
The present invention relates to methods for planning/controlling the motion of a robot, and various systems and sub-components related to the operation thereof.
2. Discussion of Background Information
Various methods have been disclosed in the literature for providing a geometric model of the xe2x80x9camount of free spacexe2x80x9d, a robot has to move within, and for producing a motion plan for the robot to move from a start position to a goal position within the free space. Approximate decomposition methods are among such methods for modeling a robot""s free space, as disclosed by Jean-Claude Latombe in xe2x80x9cRobot Motion Planning,xe2x80x9d Kluwer Academic Publishers, Boston/Dordrecht/London (1991), the content of which is expressly incorporated herein by reference in its entirety. Approximate cell decomposition may be utilized to determine the amount of free space in a given physical environment. In some such methods, a rectangloid (i.e., a rectangle or parallelepiped) decomposition P is formed of xcexa9=Cl(R), which is a rectangloid of Rm, where m is the dimension of the configuration space. The resulting rectangloid decomposition P is utilized to search for a solution path connecting a start position Qinit to a goal position Qgoal. An algorithm that may be utilized to find the solution path is as follows:
(1) An initial rectangloid decomposition P1 of a rectangloid xcexa9 within R is computed, and cells are thus produced, each of which is classified as: empty, if it does not intersect a C-obstacle region; full, if it is entirely contained in a C-obstacle region; and mixed if it partially intersects a C-obstacle region.
(2) The resulting decomposition Pi is searched in order to obtain a channel that connects the initial cell containing Qinit to the goal cell containing Qgoal. The channel may either be an E-channel, comprising all empty cells, or an M-channel, comprising one or more mixed cells. If the outcome of the search is an E-channel, the algorithm will return with the free-space empty cell E-channel. If, however, the outcome of the search is an M-channel, the process will proceed to step (3) below. Otherwise, the algorithm will return with failure.
(3) For every mixed cell within a generated M-channel, a further rectangloid decomposition Pi will be computed, and the process will return to step (2).
In computing a rectangloid decomposition of a MIXED cell, a divide-and-label method may be performed, as illustrated in FIG. 1. The method comprises the steps of first dividing a cell into smaller cells, as illustrated in FIG. 1, and then labeling each newly created cell according to whether it intersects a C-obstacle region. A widely used technique for decomposing a rectangloid xcexa9 into smaller rectangloids is to compute a 2m-tree decomposition. In a 2m-tree decomposition, a tree is formed having nodes, each of which represents a rectangloid cell which is labeled as either EMPTY, FULL or MIXED. The root node of the tree is xcexa9. Each node which represents a MIXED cell will then be decomposed to form 2m children nodes. Each child of a parent cell has the same dimensions, and is formed by dividing each edge of the parent cell into two segments of equal length. If m=3, the tree is called an octree.
FIG. 1 shows an octree decomposition of a parallelepiped representation 10 of a portion of configuration space, and displays a portion of an octree graph 12. The overall height h of the tree (i.e., the depth of the deepest node) determines the resolution of the decomposition, and hence the size of the smallest cells in the decomposition. A maximum height hmax of the tree may be specified to thereby limit the iterative process carried out by steps 2 and 3 of the algorithm noted above.
It is noted that octree graph 12 does not correspond precisely to the parallelepiped 10 depicted in FIG. 1. Rather, the various rectangloids depicted in octree graph 12 are chosen randomly in order to simplify the illustration.
The above described approximate cell decomposition method utilizes a configuration space approach to spatial planning, whereby the position and orientation of an object A in relation to obstacles B is characterized as a single point in a configuration space, in which the coordinates of the point represent a degree of freedom of the object in relation to the obstacles. The configurations (i.e., the placements) forbidden to the object A, due to the presence of other objects/obstacles, are characterized as regions in the configuration space, called configuration space obstacles (C-obstacles). Much literature has been published concerning the use of a configuration-space representations of an object with respect to obstacles, including a paper by Tomas Lozano-Perez, entitled xe2x80x9cSpatial Planning: A Configuration Space Approachxe2x80x9d, IEEE Transactions on Computers, Vol. C-32, No. 2 (February 1983), the content of which is expressly incorporated by reference herein in its entirety. This paper presents several algorithms for computing configuration space obstacles formed by objects which are polygons or polyhedra.
FIG. 2A illustrates a two-dimensional representation of a peg 26 and a hole 28, wherein the goal is to place peg 26 within hole 28, so that a bottom surface 27 of peg 26 makes flush contact with a bottom surface g of hole 28. The position and orientation of peg 26 may be represented in two-dimensional euclidian space as a set of Cartesian coordinates (x,y,xcex8), the origin of which is positioned at the center of bottom surface 27 of peg 26. At the location illustrated in FIG. 2A, peg 26 will have the coordinates xcex8=0, x=0, and y=0.
FIG. 2B illustrates a configuration space representation of the real-space problem of FIG. 2A. A point P is shown in its initial position (as shown in FIG. 2B) and may be moved to any position along a portion G of C-surface 29. C-surface 29 represents a C-obstacle 30 that corresponds to an obstacle (hole) 31 represented in real-space in FIG. 2A, and point P represents peg 26.
The position of P determines the position of peg 26 in relation to hole 28. The boundary of the shaded area shown in FIG. 2B represents the positions at which peg 26 would be in contact with obstacle 31, if point P was along the boundary. The transformation from FIG. 2A to FIG. 2B amounts to shrinking the peg 26 to a point P, and expanding obstacle 31 to form a C-obstacle 30. The transformation from FIG. 2A to FIG. 2B is a limited example of how one may reformulate a problem of moving a rigid object among other rigid objects as an equivalent problem of moving a point among transformed objects in a higher-dimensional space called the configuration space (C-space).
It is noted that FIG. 2B corresponds to the points at which peg 26 will collide with obstacle 31, if the axes (x,y) of peg 26 and hole 28 are constrained to be parallel, thereby keeping xcex8 equal to 0.
FIG. 2C illustrates how the C-surface changes as the orientation of peg 26, with respect to hole 28, changes, i.e., as xcex8 increases from 0 by rotating the orientation of peg 26 in a counter-clockwise direction. FIG. 2C thus shows in a three-dimensional C-space (x,y,xcex8) the configurations of peg 26 with respect to hole 28. In this space, hole 28 is defined as a C-obstacle. The lines illustrated in FIG. 2C represent surfaces at which some surface of peg 26 is just touching a surface of hole 28.
Another approach to motion planning may be utilized by which the configuration is discretized into a fine regular grid of configurations, and is then searched for a free path from an initial position Qinit to a goal location Qgoal. In searching the grid for a free path, several types of heuristics have been proposed. Latombe notes in xe2x80x9cRobot Motion Planningxe2x80x9d (1991) that the most successful types of heuristics, for searching a fine regular grid of configurations for a free path, include the use of functions that are interpreted as xe2x80x9cpotential fieldsxe2x80x9d. The functions are called xe2x80x9cpotential fieldsxe2x80x9d because the robot is represented as a point in configuration space which can be viewed as a particle moving under the influence of an artificial potential produced by the goal configuration (i.e., the point within the configuration space at which the point representing the robot will be at the goal) and the C-obstacles. Typically, the goal configuration generates an xe2x80x9cattractive potentialxe2x80x9d which pulls the robot toward the goal, and the C-obstacles produce a xe2x80x9crepulsive potentialxe2x80x9d which pushes the robot away from them. The direction of the resulting force is considered to be the most promising direction of motion.
In industry, in order to plan the gross motion of a robot which will be utilized to implement a particular process step, the robot is xe2x80x9cwalked throughxe2x80x9d the needed movements to bring the robot from a starting position to a goal position. Automated gross motion planning systems may be utilized to simulate the movement of the robot on a computer. However, in industry, automatically generated robot motion plans are seldom (if ever) used because the accuracy of such plans is not trusted and/or because the algorithms used to generate such plans are complicated and time-consuming.
In academics, many sophisticated automated robot motion planning algorithms have been proposed. However, a common focus in academia is to obtain optimal results, i.e., to generate a robot motion plan that moves the robot along the most efficient path from an initial position to a goal position. Since such methods concentrate on the obtention of optimal results, the resulting algorithms tend to be complicated and time-consuming.
For purposes of clarification, and to assist readers in an understanding of the present invention, a number of terms used herein are defined as follows:
Bending Apparatus/Bending Workstationxe2x80x94a workstation or apparatus for performing modern sheet metal working functions, including bend operations.
Bending Sheets of Malleable Materialxe2x80x94working of sheets of malleable material, such as sheet metal, including, but not limited to, up-action air bending, V bending, R bending, hemming, seaming, coining, bottoming, forming, wiping, folding type bending, custom bending and so on.
Maximal Overlapping Rectangloidxe2x80x94a rectangloid with its sides expanded in each orthogonal direction to the maximum possible location within a defined free space, such as described below in the text corresponding to FIG. 11D.
m-Tree Representation of a Work Spacexe2x80x94a decomposition of a rectangloid representative of a work space into smaller rectangloids, such decomposition being utilized to represent which portions of the work space rectangloid are empty, full, or mixed. The resulting decomposition being defined in terms of a tree. An example of an octree representation of a work space, which is a type of m-tree representation, is given in FIG. 1 and FIG. 11A and 11B.
Rectangloidxe2x80x94a rectangle in a two-dimensional space, or a parallelepiped in a three-dimensional space.
In view of the above, the present invention, through one or more of its various aspects and/or embodiments, is thus presented to bring about one or more objects and advantages, such as those noted below.
It is an object of the present invention to provide a computer-implemented robot motion planner for planning the motion of a robot within an industrial environment such as within a sheet metal bending work station. It is an object of the present invention to provide such a gross motion planning system which generates a motion plan in an efficient and timely manner, without excessively infringing upon the computer""s resources, such as memory.
It is a further object of the present invention to provide an automated intelligent motion planning system. The motion planning system may be provided with one or more mechanisms for adjusting the optimal nature of the resulting motion path for the robot so that, depending on the circumstances, an optimal, more refined computation method will be utilized, or a cruder but faster computation method will be utilized, in order to produce a motion path.
It is a further object of the present invention to provide mechanisms for modeling the relevant Euclidean space of the environment within which the robot is placed, the mechanism utilizing a small amount of memory space to fully represent the Euclidean space, and being configured to accurately represent the Euclidean space with a sufficient amount of resolution so that the system will be able to operate efficiently, and without the occurrence of collisions between the robot and any physical components.
It is a further object of the present invention to provide a motion planning system having a collision checking procedure which can be performed in order to determine if a collision will likely result by simulating movement of the robot in accordance with the generated motion plan. If a collision will likely occur based upon collision checking, the plan may then be modified accordingly.
It is a further object of the present invention to provide a motion planning system which interacts with, and thereby helps, other systems and subsystems in the development of a sequence plan. The motion planning system provides incremental advice to a sequence planning system in order to guide the planning process. The advice is provided in terms of explicit costs and parameters that may be used to program the final robot motion. The motion planning system also serves as a guide for various subsystems which work together with the sequence planning system to create a plan toward a final goal. The subsystems can query the motion planning system about costs and parameters associated with a particular proposed motion, and use the information provided by the motion planning system in order to development several subplans. A motion planning system of this type is in contrast from other motion planning systems that are essentially stand-alone motion planners. Such stand-along motion planners do not provide advice to other systems and subsystems about the costs and parameters associated with various moves.
The present invention, therefore, is directed to various methods and systems, including a computerized method for planning motion of a robot within free space, the free space being confined by obstacles, and the motion being planned from an initial position to a goal position. A plurality of proposed movements are proposed for an mth movement within a sequence of movements to be made by the robot. At least a portion of the robot and the obstacles that confine the free space are modeled, and a determination is made as to whether a collision will occur between the robot and an obstacle for a proposed movement being executed as the mth movement. A plan is then generated, including the sequence of movements, by choosing, for each movement in the sequence of movements, a proposed movement that will not result in a collision and that will bring the robot closer to the goal position. The robot may comprise a robot for holding and maneuvering a workpiece through a sequence of bending operations to be performed by a bending apparatus.
In accordance with a particular aspect of the present invention, the method may further include a step of estimating a cost to be associated with each proposed movement, whereby the generating step comprises choosing, for each movement in the sequence of movements, a proposed movement that will not result in a collision, that will bring the robot closer to the goal position, and that has a lowest/lower estimated cost. The estimated cost for a particular proposed movement may include a Euclidian distance to the goal position from the position of the robot after the particular proposed movement is made as the mth movement. In addition, or in the alternative, the estimated cost for a particular proposed movement may comprise an estimated value indicative of the robot travel time to move from a position after an (mxe2x88x921)th movement to a position of the robot after the particular proposed movement is made (for the mth movement).
Additional steps may be provided before the proposing step, such additional steps including specifying a plurality of movements in C-space for an mth movement in the sequence of movements, and identifying which ones of the specified plurality of movements are feasible by performing collision checking. The proposing step may then include proposing movements from among the movements identified as feasible. In addition, the specified plurality of movements specified for an mth movement in the sequence of movements may include a plurality of movements in directions which collectively surround the position at which the robot is after the (mxe2x88x921)th movement in the sequence of movements. The specified plurality of movements for an mth movement in the sequence of movements may also comprise movements in a plurality of intelligent movement directions. In this regard, the method may be designed so that it plans the motion of the robot in order to unload a malleable workpiece from a tooling punch of a bending apparatus after completing a bend. The intelligent directions may comprise a downward movement of the robot causing the workpiece to move downward. In addition, or in the alternative, the intelligent directions may comprise a backward movement of the robot causing the workpiece to be backed out of the bending apparatus. An additional type of intelligent direction may include moving the robot to thereby cause the workpiece to change in pitch from an inclined position towards a horizontal position.
The method may further include the steps of forming an m-tree representation of a work space of the robot and computing maximal overlapping rectangloids (forming channels) within the free space of the m-tree representation of the work space. The m-tree representation may be an octree representation, and the maximal overlapping rectangloids may comprise maximal overlapping parallelepipeds.
The proposing step may include proposing, for an mth movement, a set of movements of the robot to locations that fall within a maximal overlapping rectangloid within which the robot is located immediately after an (mxe2x88x921)th movement of the sequence of movements. In this regard, the set of movements may include translating the robot to any one of eight corners of the present maximal overlapping rectangloid, and moving the robot along any one of a plurality of predetermined axes/directions which bring the robot to a position along a predetermined axis/direction coincides with the goal position.
In accordance with an additional aspect of the invention, the set of movements may comprise moving the robot in a first of three orthogonal directions to a position along the first orthogonal direction which corresponds to the goal position; moving the robot: in a second of the three orthogonal directions to a position along the second orthogonal direction which corresponds to the goal position; moving the robot in a third of the three orthogonal directions to a position along the third orthogonal direction which corresponds to the goal position; moving the robot in order to adjust a pitch of a gripper of the robot; and/or moving the robot in order to adjust both the pitch and yaw of the gripper of the robot.
In accordance with yet a further aspect of the present invention, the set of movements, from which movements may be proposed (for generation of the motion plan from the initial position to the goal position), may include moving along one of a plurality of orthogonal directions only when such movement would bring the robot to an orthogonal position that corresponds to the goal position.
In accordance with a further aspect of the present invention, the method may further include fine motion planning for planning a plurality of free-space fine motion solution paths that extend between a plurality of respective pairs of positions, qi and qg. The method may also comprise gross motion planning for planning a plurality of free-space gross motion solution paths that extend between a plurality of respective pairs of positions, Qi and Qg. The fine motion planning may comprise performing the above-noted steps of proposing, modeling, determining and generating, for each pair of positions, qi and qg. In this regard, the proposing step may comprise specifying a plurality of movements in C-space for the mth movement and identifying which ones of the specified plurality of movements are feasible by performing collision checking. The gross motion planning may comprise performing the steps of proposing, modeling, determining and generating for each pair of positions, Qi and Qg. The proposing step may comprise proposing a set of movements within a maximal overlapping parallelepiped within the free space of the robot.
In accordance with an additional aspect of the present invention, the method may calculate whether the simple collision-free path can be determined, and form a plan including movements for traversing the simple collision-free path. If a simple collision-free path can be determined, the method may inhibit operation of the steps of proposing, determining, and generating, since such time-consuming steps are unnecessary in view of the already formed simple collision-free path.
The above-listed and other objects, features, and advantages of the present invention will be more fully set forth hereinafter.